package com.lun.swordtowardoffer2.c15;

import java.util.LinkedList;
import java.util.Queue;

public class MaxAreaOfIsland {

	public int maxAreaOfIsland(int[][] grid, GetArea ga) {
		int rows = grid.length;
		int cols = grid[0].length;
		
		boolean[][] visited = new boolean[rows][cols];
		int maxArea = 0;
		
		for(int i = 0; i < rows; i++) {
			for(int j = 0; j < cols; j++) {
				if(grid[i][j] == 1 && !visited[i][j]) {
					int area = ga.getArea(grid, visited, i, j);
					maxArea = Math.max(maxArea, area);
				}
			}
		}
		
		return maxArea;
	}

	public abstract class GetArea{
		
		protected final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		
		public abstract int getArea(int[][] grids, boolean[][] visited, int i, int j);
		
		protected boolean isValid(int[][] grids, boolean[][] visited, int r, int c) {
			return r > -1 && r < grids.length &&//
					c > -1 && c < grids[0].length &&
					!visited[r][c] && grids[r][c] == 1;
		}
		
	}
	
	public class GetAreaByBFS extends GetArea{

		@Override
		public int getArea(int[][] grids, boolean[][] visited, int i, int j) {
			Queue<int[]> queue = new LinkedList<>();
			queue.add(new int[] {i, j});
			int area = 0;
			
			while(!queue.isEmpty()) {
				int[] grid = queue.poll();
				visited[grid[0]][grid[1]] = true;
				area++;
				
				for(int[] dir : DIRECTIONS) {
					int r = grid[0] + dir[0];
					int c = grid[1] + dir[1];
					
					if(isValid(grids, visited, r, c)) {
						queue.offer(new int[] {r, c});
					}
				}
			}
			return area;
		}

	}
	
	public class GetAreaByDFSStack extends GetArea{

		@Override
		public int getArea(int[][] grids, boolean[][] visited, int i, int j) {
			LinkedList<int[]> stack = new LinkedList<>();
			stack.push(new int[] {i, j});
			int area = 0;
			while(!stack.isEmpty()) {
				
				int[] grid = stack.pop();
				visited[grid[0]][grid[1]] = true;
				area++;
				
				for(int[] dir : DIRECTIONS) {
					int r = grid[0] + dir[0];
					int c = grid[1] + dir[1];
					
					if(isValid(grids, visited, r, c)) {
						stack.push(new int[] {r, c});
					}
				}
			}
			return area;
		}
		
	}
	
	public class GetAreaByDFSRecursion extends GetArea{

		@Override
		public int getArea(int[][] grids, boolean[][] visited, int i, int j) {
			int area = 1;
			visited[i][j] = true;
			
			for(int[] dir : DIRECTIONS) {
				int r = i + dir[0];
				int c = j + dir[1];
				
				if(isValid(grids, visited, r, c)) {
					area += getArea(grids, visited, r, c);
				}
			}
			
			return area;
		}
		
	}
	
}
